﻿/************************************************************************
 * AIDE - Automata Identification Engine
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     AIDE\OfflineAlgo\NFMs\RPNI.cs
 * Description  :     RPNI (Regular positive negative inference) offline DFA learning algorithm which is based on 
 *                    [P. Graćıa and J. Oncina: "Inferring regular languages in polynomial update time" (1992) and
 *                    D. Neider: "Learning Automata for Streaming XML Documents" (2007)
 *                    "Grammatical_Inference_Learning Automata and Grammars" (2010)]
 * Change log   :     -24 Sep 2013:  Initial version
 * 					  -Oct 2014: some bug fixed.
 * To Do        :     -Fix the Performance Issue (optimize the implementation)
 ************************************************************************/
using System;
using System.Collections.Generic;
using AIDE.Utils;
using SMLib.Automata.Base;
using SMLib.Automata.DFA;
using SMLib.Base;

/// <summary>
/// Offline Learning algorithms for regular languages
/// </summary>
namespace AIDE.OfflineAlgo.DFAs
{
    /// <summary>
    /// RPNI (Regular positive negative inference) offline DFA learning algorithm
    /// <remarks>
    /// This implementation is based on ["Grammatical_Inference_Learning Automata and Grammars" (2010)]
    /// </remarks>
    /// </summary>
    public class RPNI
    {
        /// <summary>
        /// A state with a Set of access string
        /// </summary>
        class Block
        {
            public Block(Word w)
            {
                this.elements = new List<Word>();
                elements.Add(w);
                accepting = false;
            }


            public Block(List<Word> elements)
            {
                this.elements = elements;
                accepting = false;
            }

            public bool accepting;

            /// <summary>
            /// List of words in this block
            /// </summary>
            public List<Word> elements;

            public override string ToString()
            {
                if (elements == null || elements.Count == 0)
                    return "";
                return elements[0].ToString();
            }

            public int ConsistantNumberOfChilds;
            public bool ConsisantAccepting;
        }

        /// <summary>
        /// Prefix Tree Accepting
        /// </summary>
        Tree<Block, ISymbol> pta;


        /// <summary>
        /// Set of accepting (positive) and rejecting (negative) words
        /// </summary>
        List<Word> sPos, sNeg;

        /// <summary>
        /// Input Alphabet
        /// </summary>
        Alphabet alph;

        /// <summary>
        /// set of blue and red nodes
        /// </summary>
        List<Tree<Block, ISymbol>.TreeNode> redNodes, blueNodes, q_b_fathers, allNodes;

        /// <summary>
        /// Constructor
        /// </summary>
        public RPNI(Alphabet alph, List<Word> sPos, List<Word> sNeg)
        {
            this.alph = alph;
            this.sPos = sPos;
            this.sNeg = sNeg;
        }

		/// <summary>
		/// Initializes a new instance of the <see cref="AIDE.OfflineAlgo.DFAs.RPNI"/> class.
		/// </summary>
		/// <param name="path">Path of file containing positive and negative samples</param>
		public RPNI(string path)	
		{
			string readingModeString = LibSetting.ConfOf ("DFASAT.ReadingMode");
			//* read the input file
			if (readingModeString != null && readingModeString == "2")
				DFA_Traces.ReadInputFile_AbbadingoFormat(path,ref sPos,ref sNeg,ref alph);
			else
				DFA_Traces.ReadInputFile(path,ref sPos,ref sNeg,ref alph);
		}

        /// <summary>
        /// Build the prefix tree acceptor
        /// </summary>
        void BuildPTA()
        {
            Block b = new Block(new List<Word>());
            b.elements.Add(new Word());
            pta = new Tree<Block, ISymbol>(new Tree<Block, ISymbol>.TreeNode(b));

            allNodes = new List<Tree<Block, ISymbol>.TreeNode>();
            allNodes.Add(pta.Root);

            //* build the prefix tree out of positive samples
            foreach (Word w in sPos)
            {
                //* start from root
                Tree<Block, ISymbol>.TreeNode root = pta.Root;
                Tree<Block, ISymbol>.TreeNode curr = root;
                //* trace the nodes on tree
                for (int i = 0; i < w.Length; i++)
                {
                    Tree<Block, ISymbol>.TreeNode tmp = curr.ChildByEdge(w[i]);
                    if (tmp == null)
                    {
                        for (int j = i; j < w.Length; j++)
                        {
                            curr.NodeObject.ConsistantNumberOfChilds++;

                            Block bl = new Block(w.Prefix(j + 1));
                            curr = curr.AddChild(bl, w[j]);
                            allNodes.Add(curr);
                        }
                        Block blc = curr.NodeObject;
                        blc.accepting = true;
                        blc.ConsisantAccepting = true;
                        break;
                    }
                    else
                        curr = tmp;

                    //* check if it is accepting
                    if (i == w.Length - 1)
                    {
                        Block blc = curr.NodeObject;
                        blc.accepting = true;
                        blc.ConsisantAccepting = true;
                    }
                }
            }

            //* initialize red node as root
            redNodes = new List<Tree<Block, ISymbol>.TreeNode>();
            redNodes.Add(pta.Root);

            //* initialize blue nodes as immediate successor of root
            blueNodes = new List<Tree<Block, ISymbol>.TreeNode>();
            foreach (Tree<Block, ISymbol>.TreeNode r in pta.Root.Childs)
                blueNodes.Add(r);

            q_b_fathers = new List<Tree<Block, ISymbol>.TreeNode>();
            foreach (Tree<Block, ISymbol>.TreeNode r in pta.Root.Childs)
                q_b_fathers.Add(pta.Root);

			System.IO.File.WriteAllText("TMP_RPNITree.dot",this.pta.ExportAsDot());
        }


        /// <summary>
        /// The learn function
        /// </summary>
        public DFA Learn()
        {
            BuildPTA();

            while (blueNodes.Count != 0)
            {
                Tree<Block, ISymbol>.TreeNode q_b, q_f;
                ChooseAndRemove(out q_b, out q_f);

                bool merged = false;
                foreach (Tree<Block, ISymbol>.TreeNode q_r in redNodes)
                {

                    int indexOfQb = 0;
                    for (int i = 0; i < q_f.Childs.Count; i++)
                        if (ReferenceEquals(q_f.Childs[i], q_b))
                            break;
                        else
                            indexOfQb++;
                    q_f.Childs[indexOfQb] = q_r;

                    if (IsCompatible(q_b, q_r, q_f))
                    {
                        //* confirm changes
                        Confirm();

                        SelectBlueNodes(q_b);
                        merged = true;
                        break;
                    }
                    else
                    {
                        //* rollback chanes
                        q_f.Childs[indexOfQb] = q_b;
                        RollBack();
                    }
                }
                if (!merged)
                    Promote(q_b);
            }

            DFA conj = BuildConjecture();
			Console.WriteLine("PRNI algorithm is done! Target DFA size:"+conj.Size);
            return conj;
        }


        #region -=[ UNDO ]=-

        void RollBack()
        {
            foreach (Tree<Block, ISymbol>.TreeNode q in allNodes)
            {
                while (q.Childs.Count != q.NodeObject.ConsistantNumberOfChilds)
                {
                    q.Childs.RemoveAt(q.Childs.Count - 1);
                    q.Edges.RemoveAt(q.Edges.Count - 1);
                }

                q.NodeObject.accepting = q.NodeObject.ConsisantAccepting;
            }
        }

        void Confirm()
        {
            foreach (Tree<Block, ISymbol>.TreeNode q in allNodes)
            {
                q.NodeObject.ConsistantNumberOfChilds = q.Childs.Count;
                q.NodeObject.ConsisantAccepting = q.NodeObject.accepting;
            }
        }

        #endregion

        /// <summary>
        /// Select blue nodes in each step.
        /// </summary>
        void SelectBlueNodes(Tree<Block, ISymbol>.TreeNode removedNode)
        {
            for (int i = 0; i < allNodes.Count; i++)
            {
                if (ReferenceEquals(allNodes[i], removedNode))
                {
                    allNodes.RemoveAt(i);
                    break;
                }
            }

            foreach (Tree<Block, ISymbol>.TreeNode q in redNodes)
            {
                foreach (Tree<Block, ISymbol>.TreeNode q_ch in q.Childs)
                {
                    bool isRed = false;
                    foreach (Tree<Block, ISymbol>.TreeNode qr in redNodes)
                        if (ReferenceEquals(qr, q_ch))
                        {
                            isRed = true;
                            break;
                        }
                    if (!isRed)
                    {
                        bool isBlue = false;
                        foreach (Tree<Block, ISymbol>.TreeNode qr in blueNodes)
                            if (ReferenceEquals(qr, q_ch))
                            {
                                isBlue = true;
                                break;
                            }
                        if (!isBlue)
                        {
                            blueNodes.Add(q_ch);

                            q_b_fathers.Add(q);
                        }
                    }
                }
            }
        }


        /// <summary>
        /// Build the conjecture in the last phase of algorithm
        /// </summary>
        /// <returns></returns>
        private DFA BuildConjecture()
        {
            DFA myDFA = new DFA(alph);
            foreach (Tree<Block, ISymbol>.TreeNode qr in redNodes)
            {
				myDFA.AddState(new DFA.DFA_State(qr.NodeObject.ToString(),qr.NodeObject.accepting));
            }
            foreach (Tree<Block, ISymbol>.TreeNode qr in redNodes)
            {
                DFA.DFA_State src = null;
                foreach (DFA.DFA_State st in myDFA.GetStates())
                {
                    if (st.Identifier.Equals(qr.NodeObject.ToString()))
                    {
                        src = st;
                        break;
                    }
                }
                for (int i = 0; i < qr.NumberOfChilds; i++)
                {
                    DFA.DFA_State dst = null;
                    foreach (DFA.DFA_State st in myDFA.GetStates())
                    {
                        if (st.Identifier.Equals(qr.Childs[i].NodeObject.ToString()))
                        {
                            dst = st;
                            break;
                        }
                    }
                    if (dst != null)
                    {
                        DFA.DFA_Transition tr = new DFA.DFA_Transition(qr.Edges[i]);
                        tr.SetDestination(dst);
                        src.Transitions.Add(tr);
                    }
                }
            }
            return myDFA;
        }

        /// <summary>
        /// Promote a node (from blue to red). Note that we already added the children of qp as blue nodes
        /// <remarks>
        /// Algorith 12.9, page 256
        /// </remarks>
        /// </summary>
        /// <param name="qp">the blue node</param>
        private void Promote(Tree<Block, ISymbol>.TreeNode q_b)
        {
            //* make it red!
            redNodes.Add(q_b);
            //* add all chiled as blue
            blueNodes.AddRange(q_b.Childs);
            //* set their father as q_b
            foreach (Tree<Block, ISymbol>.TreeNode h in q_b.Childs)
                q_b_fathers.Add(q_b);
        }

        /// <summary>
        /// Merge two nodes
        /// <remarks>
        /// Algorithm 12.11, page 257
        /// </remarks>
        /// </summary>
        /// <param name="q">a red node</param>
        /// <param name="qp">a blue node</param>
        /// <param name="q_f">father of qp</param>
        private void Merge(Tree<Block, ISymbol>.TreeNode q_r, Tree<Block, ISymbol>.TreeNode q_b, Tree<Block, ISymbol>.TreeNode q_f)
        {
            Fold(q_r, q_b);
        }

        /// <summary>
        /// Fold two nodes
        /// <remarks>
        /// Algorithm 12.12, page 258
        /// </remarks>
        /// </summary>
        /// <param name="q">a red node</param>
        /// <param name="qp">being the root of a tree</param>
        private void Fold(Tree<Block, ISymbol>.TreeNode q, Tree<Block, ISymbol>.TreeNode qp)
        {
            Block bqp = qp.NodeObject;
            if (bqp.accepting)
            {
                Block bq = q.NodeObject;
                bq.accepting = true;
            }

            for (int i = 0; i < alph.Size; i++)
            {
                Tree<Block, ISymbol>.TreeNode ch_qp_a = qp.ChildByEdge(alph[i]);
                if (ch_qp_a == null) continue;

                Tree<Block, ISymbol>.TreeNode ch_q_a = q.ChildByEdge(alph[i]);
                if (ch_q_a != null)
                {
                    Fold(ch_q_a, ch_qp_a);
                }
                else
                {
                    q.AddChild(ch_qp_a, alph[i]);
                }
            }
        }

        /// <summary>
        /// Check wheather two nodes are compatible or not, i.e. can we merge them (compatible) or not (incompatible)
        /// </summary>
        /// <param name="qp">the blue node</param>
        /// <param name="q">the red node</param>
        /// <returns></returns>
        private bool IsCompatible(Tree<Block, ISymbol>.TreeNode q_b, Tree<Block, ISymbol>.TreeNode q_r, Tree<Block, ISymbol>.TreeNode q_f)
        {
            Merge(q_r, q_b, q_f);

            //* now, check wheather this NFA accepts any rejected words or not
            for (int h = 0; h < sNeg.Count; h++)
            {
                Word testWord = sNeg[h];
                Tree<Block, ISymbol>.TreeNode cur = pta.Root;
                for (int i = 0; i < testWord.Length; i++)
                {
                    cur = cur.ChildByEdge(testWord[i]);
                    if (cur == null)
                        break;
                }
                if (cur != null)
                {
                    if (cur.NodeObject.accepting)
                        return false;
                }
            }
            return true;
        }

        /// <summary>
        /// Choose the smallest blue node and remove it from the set of blue nodes
        /// </summary>
        /// <returns></returns>
        private void ChooseAndRemove(out Tree<Block, ISymbol>.TreeNode q_b, out Tree<Block, ISymbol>.TreeNode q_f)
        {
            //* select the minimum blue node
            WordsLexicoComparer comp = new WordsLexicoComparer(alph);
            Tree<Block, ISymbol>.TreeNode min = blueNodes[0], minFather = q_b_fathers[0];
            int minIndex = 0;
            for (int i = 1; i < blueNodes.Count; i++)
            {
                if (comp.Compare(min.NodeObject.elements[0], blueNodes[i].NodeObject.elements[0]) > 0)
                {
                    min = blueNodes[i];
                    minFather = q_b_fathers[i];
                    minIndex = i;
                }
            }
            
			//* remove it from blue node
            blueNodes.RemoveAt(minIndex);
            q_b_fathers.RemoveAt(minIndex);

            q_b = min;
            q_f = minFather;
        }
    }
}